package com.future.interview;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 面试题 16.21. 交换和
 * 给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
 * <p>
 * 返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-swap-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 示例:
 * <p>
 * 输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
 * 输出: [1, 3]
 * 示例:
 * <p>
 * 输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
 * 输出: []
 *
 * @author weiruibai.vendor
 * Date: 2022/12/20 10:38
 */
public class Solution_1621 {
    private static Solution_1621 INSTANCE = new Solution_1621();

    public static void main(String[] args) {
        int[] array1 = new int[]{4, 1, 2, 1, 1, 2};
        int[] array2 = new int[]{3, 6, 3, 3};
      /*  array1 = new int[]{1, 2, 3};
        array2 = new int[]{4, 5, 6};*/


        INSTANCE.findSwapValues(array1, array2);
    }

    /**
     * array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
     * sum1 = 11   sum2 = 15
     * average = 13
     *
     * @param array1
     * @param array2
     * @return
     */
    public int[] findSwapValues(int[] array1, int[] array2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        int sum1 = 0;
        for (Integer num : array1) {
            sum1 += num;
            list1.add(num);
        }
        list1.sort((o1, o2) -> o1 - o2);
        int sum2 = 0;
        for (Integer num : array2) {
            sum2 += num;
            list2.add(num);
        }
        list2.sort((o1, o2) -> o2 - o1);
        if ((sum1 + sum2) % 2 != 0) {
            return new int[]{};
        }
        int average = (sum1 + sum2) / 2;
        /**
         * 从数组list1，升序
         */
        for (Integer delete : list1) {
            /**
             * delete 小-->大
             * rest 大-->小
             */
            int rest = sum1 - delete;
            /**
             * needAdd 小-->大
             */
            int needAdd = average - rest;
            if (needAdd > list2.get(0)) { // 要判断，否则超时
                return new int[]{};
            }
            if (list2.contains(needAdd)) {
                return new int[]{delete, needAdd};
            }
        }
        return new int[]{};
    }

}
